package com.lecoboy.algorithm;

/**
 * TODO 直接插入排序(内部排序、O(n2)、稳定)
 * 原理：从待排序的数中选出一个来，插入到前面的合适位置。
 */
public class InsertSort {
    static int data[] = {9, 2, 7, 19, 100, 97, 63, 208, 55, 78};

    public static void main(String[] args) {
        print();
        System.out.println();
        insertSort();
        System.out.println();
        //print();
    }

    /**
     * 从第一个元素开始，该元素可以认为已经被排序；
     * 取出下一个元素，在已经排序的元素序列中从后向前扫描；
     * 如果该元素（已排序）大于新元素，将该元素移到下一位置；
     * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
     * 将新元素插入到该位置后；
     * 重复步骤2~5
     */
    public static void insertSort() {

        int tmp, j = 0;
        for (int k = 0; k < data.length; k++) { //---1---
            //当前值赋值给tmp
            tmp = data[k];

            System.out.println("|- k="+k+" tmp="+tmp);

            //循环k之前的值
            j = k - 1;
            //当索引值>=0和当前值小于索引值时结束循环
            while (j >= 0 && tmp < data[j]) { //---2----
                System.out.println("|  |- j="+j+" data[j]="+data[j]);
                data[j + 1] = data[j];
                j--;

            }


            data[j + 1] = tmp;//---3 ---
            print();
            System.out.println();
            System.out.println();
        }
    }
    static void print(){
        for (int i=0;i<data.length;i++){
            System.out.print(data[i]+ " ");
        }
    }
}
